/**定义一个二维数组 N*M ，如 5 × 5 数组下所示：


int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};


它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。
**/
import java.util.*;

class Point {
    int px;
    int py;
    Point father;
    Point(int px,int py,Point father) {
        this.px = px;
        this.py = py;
        this.father = father;
    }
}

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    private static void print(Point point) {
        if(point != null) {
            print(point.father);
            System.out.println("(" + point.px + "," + point.py + ")");
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { 
            //输入
            int row = in.nextInt();
            int col = in.nextInt();
            int[][] arr = new int[row][col];
            for(int i = 0;i<row;i++) {
                for(int j = 0;j<col;j++) {
                    arr[i][j] = in.nextInt();
                }
            }
            Queue<Point> queue = new LinkedList<>();
            queue.offer(new Point(0,0,null));
            Point point = null;
            arr[0][0] = 1;
            while(true) {
                point = queue.poll();
                int px = point.px;
                int py = point.py;
                if(px == row-1 && py == col -1) {
                    break;
                }
                //上
                if(px-1>=0&&arr[px-1][py] == 0) {
                    arr[px-1][py] = 1;
                    queue.offer(new Point(px-1,py,point));
                }
                //下
                if(px+1<row&&arr[px+1][py] == 0) {
                    arr[px+1][py] = 1;
                    queue.offer(new Point(px+1,py,point));
                }
                //左
                if(py-1>=0&&arr[px][py-1] == 0) {
                    arr[px][py-1] = 1;
                    queue.offer(new Point(px,py-1,point));
                }
                //右
                if(py+1<col&&arr[px][py+1] == 0) {
                    arr[px][py+1] = 1;
                    queue.offer(new Point(px,py+1,point));
                }
            }
            print(point);
        }
    }
}

